package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 */

/**
 * 这道题的关键在于，不能改变原是数组的顺序
 * 因此，不能使用 排序 + used 数组的方式进行去重
 * 这里采用 hashset 的方式进行去重
 * 在树枝上，用 startIndex 的方式进行去重
 * 在层上，用 hashset 的方式进行去重，由于 每一层是进行单独去重，因此不用将其设置为全局变量或者将其传入下一层遍历
 */

public class NonDecreasingSubsequences {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> findSubsequences(int[] nums) {
            backtracking(nums, 0);
            return res;
        }

        public void backtracking(int[] nums, int startIndex){
            // 不用 return，startIndex 的自增也会终止迭代
            if(path.size() > 1) res.add(new ArrayList<>(path));

            Set<Integer> set = new HashSet<>();

            for(int i = startIndex; i < nums.length; i++){
                if(!path.isEmpty() && nums[i] < path.get(path.size()-1)) continue;
                if(set.contains(nums[i])) continue;
                path.add(nums[i]);
                set.add(nums[i]);
                backtracking(nums, i+1);
                path.remove(path.size()-1);
            }
        }
    }
}
